package offer;
//数组中出现次数超过一半的数字
public class T29 {
    public int MoreThanHalfNum_Solution(int [] array) {
         int x = 0;
         int num = -1;
         if (array.length==0) return 0;
        for (int i = 0; i < array.length; i++) {
            if (x==0) {
                num = array[i];
                x++;
            }else {
                if (num==array[i]) x++;
                else x--;
            }
        }
        int ans = 0;
        for (int i = 0; i < array.length; i++) {
            if (num==array[i]) ans++;
        }
        return ans>array.length/2?num:0;
    }
    public int MoreThanHalfNum_Solution2(int [] array) {
         if (array.length==0) return 0;
         class  Hash{
             private int key[];
             private int val[];
             private int len;
             public Hash(int len) {
                 if (len<0x3ff) len = 1024;
                 this.len = len;
                 key = new int[len];
                 val = new int[len];
             }
             public int put(int key) {
                 int num = key&0x3ff;
                 while (key!=this.key[num]&&this.val[num]>0) num=(num+1)%len;
                 if (this.val[num]==0) {
                     this.key[num]=key;
                     this.val[num]++;
                     return this.val[num];
                 } else {
                     this.val[num]++;
                     return this.val[num];
                 }
             }
         }
         Hash hash = new Hash(array.length);
        for (int i = 0; i < array.length; i++) {
             if (hash.put(array[i])>array.length/2) return array[i];
        }
         return 0;
    }

    public static void main ( String[] args) {
           System.out.println( new T29().MoreThanHalfNum_Solution(new int[]{1,2,3,2,2,2,5,4,2}));
        System.out.println( new T29().MoreThanHalfNum_Solution2(new int[]{1}));


    }
}
